package 递归回溯.二维版;

import com.alibaba.fastjson.JSON;

public class No37解数独 {

    /**
     * 编写一个程序，通过填充空格来解决数独问题。
     * 一个数独的解法需遵循如下规则：
     * 数字 1-9 在每一行只能出现一次。
     * 数字 1-9 在每一列只能出现一次。
     * 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
     * 空白格用 '.' 表示。
     * 一个数独。
     * 答案被标成红色。
     * 提示：
     * 给定的数独序列只包含数字 1-9 和字符 '.' 。
     * 你可以假设给定的数独只有唯一解。
     * 给定数独永远是 9x9 形式的。
     */

    //行
    boolean[][] row = new boolean[9][9];
    //列
    boolean[][] col = new boolean[9][9];
    //方格
    boolean[][] box = new boolean[9][9];
    private char[][] arr;

    public void solveSudoku(char[][] board){
        this.arr=board;
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if(board[i][j]!='.') {
                    //存入已存在数字
                    //第几行
                    int xIndex = i;
                    //第几列
                    int yIndex = j;
                    //第几个盒子
                    /**
                     * 重点:
                     * [x/3] 当前排越过几个  [y/3]几个竖排[*3]=上面排越过几个
                     */
                    int boxIndex = i / 3 + (j / 3)*3;
                    //行
                    row[xIndex][board[i][j]-'1'] = true;
                    //列
                    col[yIndex][board[i][j]-'1'] = true;
                    //盒子
                    box[boxIndex][board[i][j]-'1'] = true;
                }
            }
        }
        //开始递归
        dfsMy(0,0);
    }

    /**
     * 当前点可选数字
     */
    private boolean dfsMy(int startX,int startY){

        if(startX==9){
            return true;
        }

        if(startY==9){
            return dfsMy(startX+1,0);
        }

        int boxIndex=(startX/3)+(startY/3)*3;

        for (int i = 0; i < 9; i++) {
            //开始填入1~9
            if(arr[startX][startY]!='.'){
                //当前位置已有数字,回溯
                return dfsMy(startX,startY+1);
            }
            if(row[startX][i]||col[startY][i]||box[boxIndex][i]){
                //填入当前数字不符合行列盒规则
                continue;
            }
            row[startX][i]=true;
            col[startY][i]=true;
            box[boxIndex][i]=true;
            arr[startX][startY]= (char) (i+'1');
            boolean resultFlag = dfsMy(startX, startY+1);
            if(resultFlag){
                return true;
            }
            row[startX][i]=false;
            col[startY][i]=false;
            box[boxIndex][i]=false;
            arr[startX][startY]='.';
        }
        //当前位置都没有符合的数字,前面填入的错了,false进行回溯
        return false;
    }

    public static void main(String[] args) {
        No37解数独 n=new No37解数独();
        char[][] arr={{'5','3','.','.','7','.','.','.','.'},{'6','.','.','1','9','5','.','.','.'},{'.','9','8','.','.','.','.','6','.'},{'8','.','.','.','6','.','.','.','3'},{'4','.','.','8','.','3','.','.','1'},{'7','.','.','.','2','.','.','.','6'},{'.','6','.','.','.','.','2','8','.'},{'.','.','.','4','1','9','.','.','5'},{'.','.','.','.','8','.','.','7','9'}};
        n.solveSudoku(arr);
        System.out.println(JSON.toJSONString(arr));
    }

}
